package myTest.linckedList;

import junit.framework.Assert;

import org.junit.Test;

/*
 题四、只给定单链表中某个结点p(并非最后一个结点，即p->next!=NULL)指针，删除该结点。
 办法很简单，首先是放p中数据,然后将p->next的数据copy入p中，接下来删除p->next即可。

 题五、只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。
 办法与前者类似，首先分配一个结点q，将q插入在p后，接下来将p中的数据copy入q中，然后再将要插入的数据记录在p中。

 题六、给定单链表头结点，删除链表中倒数第k个结点。
 使用两个节点p1,p2，p1初始化指向头结点，p2一直指向p1后第k个节点，两个结点平行向后移动直到p2到达链表尾部(NULL),然后根据p1删除对应结点。

 */
public class LinkedListTest {
	/**
	 * 题三、 给定单链表(head)，如果有环的话请返回从头结点进入环的第一个节点。<br>
	 * 运用题一，我们可以检查链表中是否有环。 如果有环，那么p1p2重合点p必然在环中。<br>
	 * 从p点断开环，方法为：p1=p, p2=p->next, p->next=NULL。此时，原单链表可以看作两<br>
	 * 条单链表，一条从head开始，另一条从p2开始，于是运用题二的方法，我们找到它们的第一个 交点即为所求。
	 */
	@Test
	public void test3() {
		Node head = LinkedListMaker.getNormalLists();
		LinkedListUtil.display(head);
		System.out.println("=======================");
		head = LinkedListUtil.reverse(head);
		LinkedListUtil.display(head);
	}

	/**
	 * 题二、 给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。
	 * 如果head1==head2，那么显然相交，直接返回head1。
	 * 否则，分别从head1,head2开始遍历两个链表获得其长度len1与len2。假设len1>=len2，<br>
	 * 那么指针p1由head1开始向后 移动len1-len2步。指针p2=head2，下面p1、p2每次向后前<br>
	 * 进一步并比较p1p2是否相等， 如果相等即返回该结点，否则说明两个链表没有 交点。
	 */
	@Test
	public void test2() {
		Node n1, n2;
		Node[] nodes = LinkedListMaker.getIntersectLists();
		n1 = nodes[0];
		n2 = nodes[1];
		Node node = LinkedListUtil.isIntersected(n1, n2);
		System.out.println(node);
		Assert.assertNotNull(node);
	}

	/**
	 * 题一、 给定单链表，检测是否有环。 使用两个指针p1,p2从链表头开始遍历，<br>
	 * p1每次前进一步，p2每次前进两步。 如果p2到达链表尾部，说明无环，否则<br>
	 * p1 、p2必然会在某个时刻相遇(p1==p2)，从而检测到链表中有环。
	 */
	@Test
	public void test1() {
		Node head = LinkedListMaker.getCycleList();
		boolean b = LinkedListUtil.isCycle(head);
		Assert.assertEquals(true, b);
	}

}
